package test;
import java.util.Arrays;

public class SubString {
	public static void main(String[] args) {
		System.out.println(searchKMP("12343466", "346"));
	}

	public static int searchKMP(String text, String pat) {
		int m = pat.length(), n = text.length();
		int[][] dfa = new int[256][m];

		for (int i = 0; i < m; i++) {
			dfa[pat.charAt(i)][i] = i + 1;
		}

		int i, j = 0;
		for (i = 0; i < n && j < m; i++) {
			j = dfa[text.charAt(i)][j];
		}
		if (j == m)
			return i - m;

		return n;
	}

	public static int searchBruteForce2(String text, String pat) {
		int j = 0, i = 0, m = pat.length(), n = text.length();
		for (i = 0; i < n && j < m; i++) {
			if (text.charAt(i) != pat.charAt(j)) {
				i -= j;
				j = 0;
			} else {
				j++;
			}
		}

		if (j == m) {
			return i - j;
		}

		return n;
	}

	public static int searchBruteForce1(String text, String pat) {
		int m = pat.length(), n = text.length();
		for (int i = 0; i < n; i++) {
			int j;
			for (j = 0; j < m; j++) {
				if (text.charAt(i + j) != pat.charAt(j))
					break;
			}

			if (j == m)
				return i;
		}

		return n;
	}

	private static void print(final int[] nums) {
		System.out.println(Arrays.toString(nums));
	}

	private static void print(String str) {
		System.out.println(str);
	}
}


